//
// Created by liyf on 2021/6/15.
//

#ifndef INC_2_3TREE2_NODE_H
#define INC_2_3TREE2_NODE_H

#include <iostream>
#include <array>
#include <cmath>
#include <vector>

using namespace std;

class Node{
public:
    array<Node*,4> children{};
    int szC;
    Node * parent;
    array<int,4> values{};
    int szA;
    Node(){
        parent = nullptr;
        children = {0};
        szC = 0;
        values = {0};
        szA = 0;
    }
    Node(Node * parent,int value):Node(){
        this->parent = parent;
        values[0] = value;
        szA++;
    }
    void insertValue(int value);
    void removeValue(int index);
    void onlyValue(int index);
    void insertNode(Node & pNode);
    void insertNode(int value);
    void mergeNode();
    void removeNode(int index);
    void removeNode(Node & pNode);
    void onlyNode(int index);
    int getChildValue(int index);
    void clearNode();
    void checkArr();
    void print();
    Node * findMin();  //找最小子节点
    Node * findMax();
    Node * getSuccessor(int index);  //找后继中继后继节，index为下标
    Node * getBefore(int index);
    void pushBefore(Node * successor, int index);  //往前推
    void pushSuccessor(Node * before);   //往后推
    int findAndDelete();
    void judgeAndDeleteChild();
};

void Node::insertValue(int value) {
    if(szA == 0){
        values[0] = value;
        szA++;
    } else {
        for(int i = 0; i < szA; i++){
            if(value < values[i]){
                for(int j = szA; j > i; j--)
                    values[j] = values[j - 1];
                values[i] =value;
                break;
            } else if(i == szA - 1){
                values[szA] = value;
            }
        }
        szA++;
    }
}
void Node::removeValue(int index){
    for(int i = index; i < 4 -1; i++){
        values[i] = values[i + 1];
    }
    szA--;
}
//保留这个删除其他
void Node::onlyValue(int index){
    values[0] = values[index];
    szA = 1;
}
void Node::insertNode(Node & pNode){
    Node * node = &pNode;
    node->parent = this;
    if(szC == 0) {
        this->children[0] = node;
    } else {
        int value = node->values[0];
        for(int i = 0; i < szC; i++){
            if(value < children[i]->values[0]){
                for(int j = szC; j > i; j--)
                    children[j] = children[j - 1];
                children[i] = node;
                break;
            } else if(i == szC - 1){
                children[szC] = node;
            }
        }
    }
    szC++;
}
void Node::insertNode(int value){
    this->insertNode(*new Node(this, value));
}
//合并子节点，用在删除节点，当有4个子节点使用
void Node::mergeNode(){
    Node * middle = this->children[1];
    middle->insertValue(this->getChildValue(2));
    this->removeNode(2);
}
//移除节点
void Node::removeNode(int index){
    for(int i = index; i < szC - 1;i++){
        children[i] = children[i+1];
    }
    children[szC-1] = nullptr;
    szC--;
}
void Node::removeNode(Node & pNode){
    for(int i = 0; i < szC-1;i++){
        if(children[i] == &pNode){
            this->removeNode(i);
            break;
        }

    }
}
//保留这个移除其他
void Node::onlyNode(int index){
    children[0] = {children[index]};
    szC = 1;
}
//清空子节点
void Node::clearNode(){
    children = {0};
    szC = 0;
}
//获取相应子节点的第一个值
int Node::getChildValue(int index){
    if(children[index])
        return children[index]->values[0];
    return 0;
}
void Node::checkArr() {
    //只有根节点
    if(szA == 3 && parent == nullptr){
        this->insertNode(values[0]);
        this->insertNode(values[2]);
        //根节点只剩中间值
        this->onlyValue(1);
    }
    //父节点为2节点
    else if(szA == 3 && parent->szC == 2){
        //中间值添加进父节点，并移除自己的中间值
        parent->insertValue(values[1]);
        //当前节点移除添加的值
        this->removeValue(1);
        //右型
        if(parent->children[1] == this){
            //左值添加为父节点的左节点，并移除自己的左值
            Node * newNode = new Node(parent,values[0]);
            //移除添加的值，方便父节点根据子节点的第一个数排序
            this->removeValue(0);
            parent->insertNode(*newNode);
        }
        //左型
        else if(parent->children[0] == this){
            //右值添加为父节点的右节点，并移除自己的右值
            Node * newNode = new Node(parent, values[1]);
            //移除添加的值，方便父节点根据子节点的第一个数排序
            this->removeValue(1);
            parent->insertNode(*newNode);
        }
    }
    //父节点为3节点
    else if(szA == 3 && parent->szC == 3){
        //父节点变为4节点
        parent->insertValue(this->values[1]);
        //移除添加的值
        this->removeValue(1);
        //左型，中间型
        if(this == parent->children[0] || this == parent->children[1]){
            Node * newNode = new Node(parent, values[1]);
            this->removeValue(1); //当前节点值只剩一个，方便插入时排序
            parent->insertNode(*newNode);
            //如果当前节点有子节点
            if(this->szC > 0){
                newNode->insertNode(this->getChildValue(2));
                newNode->insertNode(this->getChildValue(3));
                //移除添加过的节点
                this->removeNode(3);
                this->removeNode(2);
            }
        }
        //右型
        else if(this == parent->children[2]){
            Node * newNode = new Node(parent, values[0]);
            this->removeValue(0);//当前节点值只剩一个，方便插入时排序
            parent->insertNode(*newNode);
            //如果当前节点有子节点
            if(this->szC > 0){
                newNode->insertNode(this->getChildValue(0));
                newNode->insertNode(this->getChildValue(1));
                //移除添加过的节点
                this->removeNode(1);
                this->removeNode(0);
            }
        }
        //祖父节点情况
        Node * grand = parent->parent;
        //祖父节点不为空，找更上层的节点
        if(grand){
            //祖父为2节点
            if(grand->szC == 2){
                //parent在grand左边
                Node * parent = this->parent;   //不写会出错，不知道为什么
                if(grand->children[0] == parent){
                    //grand变为3节点3
                    grand->insertValue(parent->values[1]);
                    Node * middle = new Node(grand,parent->values[2]);

                    middle->insertNode(*parent->children[2]);
                    middle->insertNode(*parent->children[3]);
                    //parent变为2节点
                    parent->onlyValue(0);
                    grand->insertNode(*middle);

                    parent->removeNode(3);
                    parent->removeNode(2);
                }
                //parent在grand右边
                else if (grand->children[1] == parent){
                    //grand变为3节点
                    grand->insertValue(parent->values[1]);
                    Node * middle = new Node(grand,parent->values[0]);

                    middle->insertNode(*parent->children[0]);
                    middle->insertNode(*parent->children[1]);

                    parent->onlyValue(2);
                    grand->insertNode(*middle);

                    parent->removeNode(1);
                    parent->removeNode(0);
                }
            }
            //祖父为3节点
            else{
                parent->checkArr();
            }
        }
        //祖父节点为空，父节点为根节点，树的高度增加
        else{
            //新增左右节点
            Node * left = new Node(parent,parent->values[0]);
            Node * right = new Node(parent, parent->values[2]);
            Node * parent = this->parent;   //不拿出来会有问题
            left->insertNode(*parent->children[0]);
            left->insertNode(*parent->children[1]);
            right->insertNode(*parent->children[2]);
            right->insertNode(*parent->children[3]);
            //父节点变为2节点
            parent->onlyValue(1);
            parent->clearNode();
            parent->insertNode(*left);
            parent->insertNode(*right);
        }
    }
}
Node *Node::findMin() {
    if(this->szC == 0)  //该节点为叶子节点
        return this;
    else    //否则找子节点
        return children[0]->findMin();
}
Node * Node::findMax() {
    if(this->szC == 0)
        return this;
    else{
        if(this->szC == 2)
            return children[1]->findMax();
        else
            return children[2]->findMax();
    }
}
Node * Node::getSuccessor(int index) {
    //当前为叶子节点
    if(this->szC == 0){
        //当前没有父节点：当前为根节点
        if(parent == nullptr)
            return nullptr;
        else {
            //当前节点为右节点
            Node * cur = this;
            Node * parent = this->parent;
            while(parent){
                //父节点为3节点，子节点为父节点的右节点
                if(parent->szC == 3 && parent->children[2] == cur){
                    cur =  parent;
                    parent = parent->parent;
                }
                //父节点为2节点，子节点为父节点的右节点
                else if(parent->szC == 2 && parent->children[1] == cur){
                    cur =  parent;
                    parent = parent->parent;
                } else{
                    return parent;
                }
            }
        }
    }
    //当前为2节点
    else if(this->szC == 2)
        //找右节点的最小节点
        return children[1]->findMin();
    //当前为3节点
    else{
        //左节点的后继节点
        if(index == 0)
            return children[1]->findMin();
        //右节点的后继节点
        else
            return children[2]->findMin();
    }
}

Node *Node::getBefore(int index) {
    //当前为叶子节点
    if(this->szC == 0){
        //当前没有父节点：当前为根节点
        if(parent == nullptr)
            return nullptr;
        else {
            //当前节点为左节点
            Node * cur = this;
            Node * parent = this->parent;
            while(parent){
                if(parent->children[0] == cur){
                    cur =  parent;
                    parent = parent->parent;
                } else{
                    return parent;
                }
            }
        }
    }
    //当前节点为2节点
    else if(this->szC == 2)
        //找左节点的最大节点
        return this->children[0]->findMax();
    //当前节点为3节点
    else{
        //按左值
        if(index == 0)
            return this->children[0]->findMax();
        //按右值
        else
            return this->children[1]->findMax();
    }
}

void Node::pushBefore(Node * successor, int index) {
    //把值按前继往前推
    Node * cur = this;
    if(index == 1){ //从右值开始
        Node * next = cur->getSuccessor(index);
        cur->insertValue(next->values[0]);
        cur = next;
    }
    while(cur != successor){
        Node * next = cur->getSuccessor(0);
        cur->values[0] = next->values[0];
        cur = next;
    }
    //移除后继的左值
    successor->removeValue(0);
    //后继有子节点
    if(successor->szC == 3) {
        //中节点，两种情况
        successor->judgeAndDeleteChild();
        return;
        Node * successorMiddle = successor->children[1];
        //中节点为2节点
        if(successorMiddle->szA == 1){
            //中节点左值插入左节点
            successor->children[0]->insertValue(successorMiddle->values[0]);
            //删除中节点
            successor->removeNode(1);
            delete successorMiddle;
        }
            //中节点为3节点
        else {
            //中节点左值插入后继节点
            successor->insertValue(successorMiddle->values[0]);
            //移除中节点左值
            successorMiddle->removeValue(0);
        }
    }
}

void Node::pushSuccessor(Node *before) {
    //把值按后继往前推
    Node * cur = this;
    while(cur != before){
        Node * next = cur->getSuccessor(0);
        cur->values[0] = next->values[0];
        cur = next;
    }
    //移除前继的右值
    before->removeValue(1);
    //前继有子节点
    if(before->szC == 3) {
        before->judgeAndDeleteChild();
        return;
        //中节点，两种情况
        Node * successorMiddle = before->children[1];
        //中节点为2节点
        if(successorMiddle->szA == 1){
            //中节点左值插入前继右节点
            before->children[2]->insertValue(successorMiddle->values[0]);
            //删除中节点
            before->removeNode(1);
            delete successorMiddle;
        }
        //中节点为3节点
        else {
            //中节点右值插入前继节点
            before->insertValue(successorMiddle->values[1]);
            //移除中节点右值
            successorMiddle->removeValue(1);
        }
    }
}
int Node::findAndDelete(){
    Node * removeNode = this;
    //找后继
    Node * successor = removeNode->getSuccessor(0);
    int successorDis = 1;
    while(successor){
        if(successor->szA == 2) break;
        successorDis++;
        successor = successor->getSuccessor(0);
    }
    //找前继
    Node * before = removeNode->getBefore(0);
    int beforeDis = 1;
    while(before){
        if(before->szA == 2) break;
        beforeDis++;
        before = before->getBefore(0);
    }
    //如果有3节点
    if(successor || before){
        //两边都有，找最近
        if(successor && before){
            //往后推
            if(beforeDis > successorDis)
                removeNode->pushSuccessor(before);
                //往前推
            else
                removeNode->pushBefore(successor,0);
        }
            //只有后继，往前推
        else if(successor)
            removeNode->pushBefore(successor,0);
            //只有前继，往后推
        else
            removeNode->pushSuccessor(before);
        return 1;
    }
    //没有后继3节点，完全2叉树，降低高度
    else {
        return 0;
    }
}

void Node::judgeAndDeleteChild() {
    Node * removeNode = this;
    //先找左边的前继
    Node * cur = removeNode->getBefore(0);
    while(cur) {
        if(cur->szA == 2 || cur == removeNode)break;
        Node * before = cur->getBefore(0);
        if(removeNode->parent == before){   //不要往父节点找
            cur = nullptr;
            break;
        }
        cur = before;

    }
    //找到了
    if(cur && cur != removeNode) {
        //往后推
        removeNode->pushSuccessor(cur);
        return;
    }
    //没找到
    //找左值的后继
    cur = removeNode->getSuccessor(0);
    while(cur) {
        if(cur->szA == 2 || cur == removeNode) break;
        Node * successor = cur->getSuccessor(0);
        if(removeNode->parent == successor){
            cur = nullptr;
            break;
        }
        cur = successor;
    }
    //找到了
    if(cur && cur != removeNode) {
        //往前推
        removeNode->pushBefore(cur,0);
        return;
    }
    //没找到，或者找到了自己
    //找右值的后继
    cur = removeNode->getSuccessor(1);
    while(cur){
        if(cur->szA == 2 || cur == removeNode) break;
        cur = cur->getSuccessor(0);
    }
    //找到了
    if(cur && cur != removeNode){
        //往前推到右值
        removeNode->pushBefore(cur,1);
        return;
    }
    //没找到，子节点全是2节点
    Node * removeMiddle = removeNode->children[1];
    //移除中节点
    removeNode->removeNode(1);
    //删除的是左值
    if(removeMiddle->values[0] < removeNode->values[0]){
        Node * removeLeft =removeNode->children[0];
        //中值插入左节点
        removeLeft->insertValue(removeMiddle->values[0]);
        //中节点的子节点插入左节点
        removeLeft->insertNode(*removeMiddle->children[0]);
        removeLeft->insertNode(*removeMiddle->children[1]);
        //左子节点合并
        removeLeft->mergeNode();
    }
        //删除的值是右值
    else{
        Node * removeRight = removeNode->children[1];
        //中值插入右节点
        removeRight->insertValue(removeMiddle->values[0]);
        //中节点的子节点插入右节点
        removeRight->insertNode(*removeNode->children[0]);
        removeRight->insertNode(*removeNode->children[1]);
        //右子节点合并
        removeRight->mergeNode();
    }
    //删除中节点
    delete removeMiddle;
}

class Tree {
public:
    Node * node;
    Tree(){
        node = new Node;
        this->clear();
    }
    //插入
    void insert(int value);
    void insert(const vector<int>& values);
    void print();
    void print(int value);
    void clear();
    Node * getNode(int value);
    void remove(int value);
};
void Tree::insert(int value) {
    if(this->node->szA == 0){
        this->node->insertValue(value);
        return;
    }

    Node * cur = node;
    while(cur->szC){
        array<int,4> arr = cur->values;
        if(value == arr[0] || value==arr[1])
            return;
        if(cur->szC == 2){
            if(value < arr[0])
                cur = cur->children[0];
            else
                cur = cur->children[1];
        } else if(cur->szC == 3){
            if(value < arr[0])
                cur = cur->children[0];
            else if(value > arr[0] && value < arr[1] && cur->szC == 3)
                cur = cur->children[1];
            else if(value > arr[1])
                cur = cur->children[2];
        }
    }

    cur->insertValue(value);
    cur->checkArr();
}
void Tree::insert(const vector<int>& values) {
    for(int value : values){
        this->insert(value);
    }
}

Node *Tree::getNode(int value) {
    Node * cur = node;
    while(cur){
        array<int,4> arr = cur->values;
        if(value == arr[0] || value==arr[1])
            return cur; //找到了
        if(cur->szC == 2){
            if(value < arr[0])
                cur = cur->children[0];
            else
                cur = cur->children[1];
        } else if(cur->szC == 3){
            if(value < arr[0])
                cur = cur->children[0];
            else if(value > arr[0] && value < arr[1] && cur->szC == 3)
                cur = cur->children[1];
            else if(value > arr[1])
                cur = cur->children[2];
        } else {
            return nullptr;
        }
    }
    //没找到
    return nullptr;
}
void Tree::print(){
    this->node->print();
}
void Tree::print(int value) {
    getNode(value)->print();
}

void Tree::remove(int value) {
    //参数
    Node * removeNode = this->getNode(value);
    if(removeNode == nullptr)
        return; //没找到
    Node* removeParent = removeNode->parent;
    //删除节点是3节点
    if(removeNode->szA == 2){
        //如果是叶子节点，移除一个值
            if(value == removeNode->values[0])
                removeNode->removeValue(0);
            else
                removeNode->removeValue(1);
        //如果有子节点，分很多情况
        if(removeNode->szC != 0){
            removeNode->judgeAndDeleteChild();
        }
    }
    //删除节点是2节点
    else if(removeNode->szA == 1){
        if(removeParent == nullptr){
            //没有子节点：根节点
            if(removeNode->szC == 0){
                delete removeNode;
                this->node = nullptr;
                return;
            }
                //有子节点
            else {
                int isBinaryTree = removeNode->findAndDelete();
                //如果是完全二叉树，降低高度
                if(isBinaryTree == 0){
                    //移除根节点的左值
                    removeNode->removeValue(0);
                    //左右节点的值插入根节点
                    Node * left = removeNode->children[0];
                    Node * right = removeNode->children[1];
                    removeNode->insertValue(left->values[0]);
                    removeNode->insertValue(right->values[0]);
                    //移除子节点
                    removeNode->clearNode();
                    //如果子节点还有子节点
                    if(left->szC != 0){
                        //插入孙子节点
                        removeNode->insertNode(*left->children[0]);
                        removeNode->insertNode(*left->children[1]);
                        removeNode->insertNode(*right->children[0]);
                        removeNode->insertNode(*right->children[1]);
                        //自动调整
                        removeNode->mergeNode();
                    }
                }
            }
        }
            //有父节点
        else{
            //父节点为3节点
            if(removeParent->szC == 3){
                //左型
                if(removeNode == removeParent->children[0]){
                    //移除该节点的值
                    removeNode->removeValue(0);
                    //添加父节点的左值
                    removeNode->insertValue(removeParent->values[0]);
                    removeParent->removeValue(0);
                    //中间兄弟节，两种情况
                    Node * removeBrother = removeParent->children[1];
                    //兄弟节点为2节点
                    if(removeBrother->szA == 1){
                        //添加兄弟节点的值
                        removeNode->insertValue(removeBrother->values[0]);
                        //删除兄弟节点
                        removeParent->removeNode(1);
                        delete removeBrother;
                    }
                        //兄弟节点为3节点
                    else {
                        //兄弟节点的左值添加到父节点
                        removeParent->insertValue(removeBrother->values[0]);
                        removeBrother->removeValue(0);
                    }
                }
                    //中间型
                else if(removeNode == removeParent->children[1]){
                    //左兄弟节点，两种情况
                    Node * removeBrother = removeParent->children[0];
                    //兄弟节点为2节点
                    if(removeBrother->szA == 1){
                        //删除当前节点
                        removeParent->removeNode(1);
                        delete removeNode;
                        //父节点左值插入兄弟节点
                        removeBrother->insertValue(removeParent->values[0]);
                        removeParent->removeValue(0);
                    }
                        //兄弟节点为3节点
                    else {
                        //父节点左值替换当前节点值
                        removeNode->values[0] = removeParent->values[0];
                        //兄弟节点右值替换父节点左值
                        removeParent->values[0] = removeBrother->values[1];
                        removeBrother->removeValue(1);
                    }
                }
                    //右型，左型的反向
                else {
                    //移除该节点值
                    removeNode->removeValue(0);
                    //添加父节点右值
                    removeNode->insertValue(removeParent->values[1]);
                    removeParent->removeValue(1);
                    //兄弟节点，两种情况
                    Node * removeBrother = removeParent->children[1];
                    //兄弟节点为2节点
                    if(removeBrother->szA == 1){
                        //兄弟节点值插入当前节点
                        removeNode->insertValue(removeBrother->values[0]);
                        //删除兄弟节点
                        removeParent->removeNode(1);
                        delete removeBrother;
                    }
                        //兄弟节点为3节点
                    else if(removeBrother->szA == 2){
                        //兄弟节点左值插入父节点
                        removeParent->insertValue(removeBrother->values[1]);
                        removeBrother->removeValue(1);
                    }
                }
            }
                //父节点为2节点
            else if(removeParent->szC == 2){
                Node * removeBrother = nullptr;
                //删除节点是左节点
                if(removeNode == removeParent->children[0]){
                    removeBrother = removeParent->children[1];
                    //兄弟节点为3节点
                    if(removeBrother->szA == 2){
                        //兄弟左值->父左值->删除左值
                        removeNode->values[0] = removeParent->values[0];
                        removeParent->values[0] = removeBrother->values[0];
                        removeBrother->removeValue(0);
                        return;
                    }
                }
                    //删除节点是右节点
                else{
                    removeBrother = removeParent->children[0];
                    //兄弟节点为3节点
                    if(removeBrother->szA == 2){
                        //兄弟右值->父左值->删除左值
                        removeNode->values[0] = removeParent->values[0];
                        removeParent->values[0] = removeBrother->values[1];
                        removeBrother->removeValue(1);
                        return;
                    }
                }
                //兄弟节点不是3节点
                if(removeBrother->szA != 2){
                    int isBinaryTree = removeNode->findAndDelete();
                    //如果是完全二叉树
                    if (isBinaryTree == 0){
                        removeParent->insertValue(removeBrother->values[0]);
                        removeParent->clearNode();
                        //有子节点
                        if(removeNode->szC == 2){
                            removeParent->insertNode(*removeNode->children[0]);
                            removeParent->insertNode(*removeNode->children[1]);
                            removeParent->insertNode(*removeBrother->children[0]);
                            removeParent->insertNode(*removeBrother->children[1]);
                            removeParent->mergeNode();
                        }
                        //删除当前节点和兄弟节点
                        delete removeNode;
                        delete removeBrother;
                        //有祖父节点
                        Node * removeGrand = removeParent->parent;
                        while(removeGrand){
                            //兄弟节点
                            Node * removeParentBrother = nullptr;
                            if(removeParent == removeGrand->children[0])
                                removeParentBrother = removeGrand->children[1];
                            else
                                removeParentBrother = removeGrand->children[0];
                            //兄弟左值插入祖父
                            removeGrand->insertValue(removeParentBrother->values[0]);
                            //兄弟子节点插入祖父
                            removeGrand->insertNode(*removeParentBrother->children[0]);
                            removeGrand->insertNode(*removeParentBrother->children[1]);
                            //删除兄弟节点
                            removeGrand->removeNode(*removeParentBrother);
                            delete (removeParentBrother);
                            removeParent = removeGrand;
                            removeGrand = removeGrand->parent;
                        }
                    }
                }
            }
        }
    }
}

#endif //INC_2_3TREE2_NODE_H
